package primary.String;

import java.util.Locale;

/**
 * @Author Elephas
 * @Date 2022/1/9
 **/
@FunctionalInterface
public interface StrStr {
    int strStr(String hayStack,String needle);
}
class StrStrImpl1 implements StrStr{

    /*
        寻找第一个出现的字串下标，考虑使用KMP算法实现.
     */
    public int strStr(String haystack,String needle){
        if(needle == null || "".equals(needle)){
            return 0;
        }
        int[] next = buildNext(needle.toCharArray());
        char[] T = haystack.toCharArray();
        char[] S = needle.toCharArray();
        int i = 0, j = 0;
        while ( j < haystack.length()){
            while( i > -1 && S[i] == T[j]){
                i = next[i];
            }
            i++;
            j++;
            if( i >= haystack.length()){
                return  j-i;
            }
        }
        return 0;
    }
    public static int[] buildNext(char[] str){
        int i,j;
        int[] next = new int[str.length];
        i = 0;
        j = next[0] = -1;
        while(i < str.length){
            while( j > -1 && str[i] != str[j]){
                j = next[j];
            }
            i++;
            j++;
            if(str[i] == str[j]){
                next[i] = next[j];
            }else{
                next[i] = j;
            }
        }
        return next;
    }
}

class StrStrImpl2 implements StrStr{

    @Override
    public int strStr(String hayStack, String needle) {
        if("".equals(hayStack)){
            if("".equals(needle)){
                return 0;
            }else{
                return -1;
            }
        }
        if("".equals(needle)){
            return 0;
        }

        int[] lps = new int[needle.length()];
        buildNext(lps, needle);
        int N = hayStack.length(), M = needle.length();
        int i = 0, j = 0;
        while (i < N) {
            if (needle.charAt(j) == hayStack.charAt(i)) {
                i++;
                j++;
            }
            if (j == M) {
                return i - j;
                // j = lps[j - 1]
            } else if (i < N && needle.charAt(j) != hayStack.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i = i + 1;
                }
            }
        }
        return -1;
    }
    private void buildNext(int[] lps,String patten){
        int M = lps.length;
        // length of the previous longest prefix suffix
        int len = 0;
        // lps[0] is always 0
        lps[0] = 0;
        int i = 1;

        // the loop calculates lps[i] for i to M -1
        while(i < M){
            if(patten.charAt(i) == patten.charAt(len)){
                len++;
                lps[i] = len;
                i++;
            }else{
                // pat[i] != pat[len]
                // This is tricky. Consider the example.
                // AAACAAAA and i = 7. The idea is similar
                // to search step.
                if(len != 0){
                    len = lps[len - 1];
                    // do not increment i here
                }else{
                    lps[i] = 0;
                    i++;
                }
            }
        }
    }
}